/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-11-18
 * Time: 9:42
 */
public class HashBuck {
    static class Node{
        private int key;
        private int value;
        private Node next;

        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    private Node[] arr;
    private int usedSize;

    //默认负载因子为0.75
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    public HashBuck(){
        this.arr = new Node[10];
    }

    /**
     * 插入哈希桶方法
     */
    public void put(int key, int val){
        Node node = new Node(key, val);
        int index = key % 10;
        Node cur = arr[index];
        //Node last = cur;
        while (cur != null){
            if (cur.key == key){
                cur.value = val;
                return;
            }
            //last = cur;
            cur = cur.next;
        }
        //尾插法
        //last.next = node;
        //头插法
        node.next = arr[index];
        arr[index] = node;
        usedSize++;
        //计算负载因子
        if (loadFactor() >= DEFAULT_LOAD_FACTOR){
            //扩容
            resize();
        }
    }

    /**
     * 扩容方法
     */
    private void resize() {
        //2倍扩容
        Node[] tmpArr = new Node[arr.length * 2];
        for (int i = 0; i < arr.length; i++){
            Node cur = arr[i];
            while(cur != null){
                int index = cur.key % tmpArr.length;
                Node curNext = cur.next; //需要记录下来cur的下一个节点的位置
                //尾插法：
//                Node indexCur = tmpArr[index];
//                while (indexCur.next != null){
//                    indexCur = indexCur.next;
//                }
//                cur.next = null;
//                indexCur.next = cur;
                //头插法
                cur.next = tmpArr[index]; //改变了cur的next
                tmpArr[index] = cur;
                cur = curNext;
            }
        }
        arr = tmpArr; //arr指向tmpArr
    }

    /**
     * 计算负载因子方法
     */
    private float loadFactor(){
        return usedSize * 1.0f /arr.length;
    }

    /**
     * 返回key对应的val方法
     */
    public int getVal(int key){
        int index = key % arr.length;
        Node cur = arr[index];
        while (cur != null){
            if (cur.key == key) return cur.value;
            cur = cur.next;
        }
        return -1;
    }
}
